def merge(listLeft, listRight):
    """
    入参数组都是有序的，此处将两个有序数组合并成一个大的有序数组
    """
    # 两个数组的起始下标
    l, r = 0, 0

    newList = []
    while l < len(listLeft) and r < len(listRight):
        if listLeft[l] <= listRight[r]:
            newList.append(listLeft[l])
            l += 1
        else:
            newList.append(listRight[r])
            r += 1
    newList += listLeft[l:]
    newList += listRight[r:]
    return newList


def mergeSort(myList):
    """归并排序
    myList: 待排序数组
    return: 新数组list
    """
    if len(myList) <= 1:
        return myList

    mid = len(myList) // 2
    listLeft = mergeSort(myList[:mid])
    listRight = mergeSort(myList[mid:])
    return merge(listLeft, listRight)


if __name__ == "__main__":
    myList = [12, 33, 199, 0, 54, 33, 11, 12]
    result = mergeSort(myList)
    print(f'归并排序后：{result}')
